package leetcode.offer0047;

public class Solution {
	public int maxValue(int[][] grid) {
		int m = grid.length, n = grid[0].length;
		for (int i = m - 1; i > -1; i--) {
			for (int j = n - 1; j > -1; j--) {
				int cur = grid[i][j];
				grid[i][j] = 0;
				if (i < m - 1)
					grid[i][j] = grid[i + 1][j];
				if (j < n - 1)
					grid[i][j] = Math.max(grid[i][j], grid[i][j + 1]);
				grid[i][j] += cur;
			}
		}
		return grid[0][0];
	}
}
